1. Field of the Invention
This invention generally relates to a high speed multiplication processing device suitable for large scale integration (LSI) thereof and more particularly to a multiplication processing device which generates partial products by recoding multipliers.
2. Description of the Related Art
First, it will be explained hereinbelow that a precision iterative multiplication can be achieved by rounding a result of a multiplication. Consider, for example, an iterative multiplication in which a result of a multiplication is used as an operand for the next multiplication. In this case, assuming that the number of digits of a multiplier which can be inputted to a multiplication processing device is n (representing a predetermined natural number), a result of a multiplication is represented by n or more digits. When the result of the multiplication is truncated to n digits and the thus obtained n-digit result of the multiplication is inputted to the device as an operand for the next multiplication, an error of less than 1 occurs in the inputted operand by comparison with the value which the result of the multiplication had before the truncation. Incidentally, the weight of the least significant digit of the operand obtained as the result of the truncation is assumed to be 1. In contrast to this, when what is called a nearest approximation rounding operation is performed and thereafter a result thereof is inputted as an operand, an error becomes 1/2 at most. This means that when a nearest approximation rounding operation is performed, the result of an iterative multiplication operation becomes more accurate than in case of truncating a result of a multiplication of the iterative multiplication operation and using the result of the truncation as an operand for the next multiplication thereof. Thereby, a precision iterative multiplication operation can be achieved. Hereinafter, a conventional iterative multiplication processing device for performing an iterative multiplication operation by effecting a rounding operation upon completion of each multiplication of the iterative multiplication operation will be described.
Referring to FIG. 9, there is illustrated the construction of the conventional iterative multiplication processing device for performing an iterative multiplication operation by effecting a rounding operation upon completion of each multiplication of the iterative multiplication operation. Reference numeral 901 indicates a selection latch; and 902, 903, 904 and 905 latches. The respective latches operate in response to two-phase clock signals ph1 and ph2. Reference numeral 906 represents a 2-bit Booth recoding circuit which divides a binary multiplier latched by the selection latch 901 from the least significant bit thereof to the most significant bit thereof into 2-bit sets and then recodes each 2-bit set as a value of from -2 to 2. Reference numeral 907 indicates a partial-product-generating-and-adding circuit for generating and adding partial products by using values which are obtained by recoding the 2-bit sets (hereunder referred to as recoding values) and outputted from the 2-bit Booth recoding circuit 906 and for outputting the result of the addition in the form of, for example, a redundant binary intermediate result. Reference numeral 908 denotes a binary number converting circuit which converts a redundant binary number into a binary number. Reference numeral 909 represents a rounding circuit for rounding the result of the multiplication, which is converted by the binary number converting circuit 908, to a predetermined digit.
Consider a case that a multiplication expressed by, for instance, the following equation (1) is performed by using the multiplication processing device of FIG. 9. EQU P.sub.n =P.sub.n-1 .times.Q.sub.n-1 ( 1)
First, P.sub.n-1 is inputted to the selection latch 901 as a multiplier. Further, Q.sub.n-1 is inputted to the latch 902 as a multiplicand. Then, the result of the multiplication expressed by the equation (1) is latched by the latch 903 as a redundant binary intermediate result. In the next cycle, this intermediate result is latched by the latch 904 and is converted by the binary number converting circuit 908 into a binary number. Thereafter, the binary intermediate result thus obtained is rounded by the rounding circuit 909 to a predetermined digit and the thus rounded intermediate result is inputted to the latch 905. Further, in the following cycle, the rounded intermediate result is inputted to the latch 901 and then the next multiplication P.sub.n .times.Q.sub.n is performed. At that time, data Q.sub.n has been latched by the latch 902.
Namely, the conventional iterative multiplication processing device which performs an iterative multiplication operation by effecting a rounding operation upon completion of each multiplication of the iterative multiplication operation, the binary number converting circuit 908 and the rounding circuit 909 are used when performing each multiplication.
Next, another conventional iterative multiplication processing device (hereunder referred to as a second conventional iterative multiplication processing device) for multiplying a multiplicand by a value obtained by subtracting a multiplier from a constant A and using the result of the multiplication as a multiplier for the next multiplication will be described hereinbelow. Referring to FIG. 10, there is illustrated the construction of the second conventional iterative multiplication processing device. Incidentally, in FIG. 10, like reference numerals designate like blocks or parts of FIG. 9. Reference numeral 1001 designates a subtracting circuit which subtracts a value selected by the selection latch 901 from the constant A.
Hereinafter, it will be described how an iterative multiplication operation of repeatedly effecting a multiplication expressed by the following equation (2) is performed by the multiplication processing circuit of FIG. 10. EQU P.sub.n =(A-P.sub.n-1).times.Q.sub.n-1 ( 2)
In a first cycle, P.sub.n-1 is inputted to the selection latch 901 as a multiplier. Then, a subtraction (A-P.sub.n-1) is performed by the subtracting circuit 1001 and the result of the subtraction is inputted to the 2-bit Booth recoding circuit 906. On the other hand, Q.sub.n-1 is inputted to the latch 902 as a multiplicand. Subsequently, partial products are generated and added by using a value obtained by recoding the multiplier. Thus, for example, a redundant binary intermediate result is generated. This intermediate result is latched by the latch 903. In a second cycle, this intermediate result is latched by the latch 904 and is then converted by the binary number converting circuit 908 into a binary number. Subsequently, a binary result of the multiplication ((A-P.sub.n-1).times.Q.sub.n-1) is latched by the latch 905. In a third cycle, the selection latch 901 selects the result of the multiplication effected in the last cycle (namely, in the second cycle) and performs a multiplication similarly as in the first cycle. Thereafter, operations effected in the second and third cycles are repeated and a binary result of the multiplication is outputted in an mth cycle (incidentally, m is an even positive integer).
As described above, in the second conventional iterative multiplication processing device for performing an iterative multiplication operation by multiplying a value obtained by subtracting the multiplier from the constant A by the multiplicand in each stage thereof and using the result of the multiplication as a multiplier for the next multiplication, a subtraction circuit for subtracting a multiplier from the constant at each multiplication.
Turning to FIG. 13, there is illustrated the construction of still another conventional iterative multiplication processing device (hereunder referred to as a third conventional iterative multiplication processing device) for multiplying a value resulted from subtracting a redundant binary intermediate product, which is obtained by the multiplication in the last cycle (namely, the cycle directly before the present cycle) from a constant, by a multiplicand. Reference numeral 1301 represents a selection circuit which selects a redundant binary number and a multiplier and latches them in response to a clock signal ph1. Reference numerals 1302, 1303, 1304 and 1305 designate latches which operate in response to clock signals ph1 and ph2. Reference numeral 1306 denotes a partial product generating circuit which generates and adds partial products from output values of a redundant binary 2-bit Booth recoding circuit 1307 and outputs of the latches 1302. The redundant binary 2-bit Booth recoding circuit 1307 partitions an output value of the redundant binary addition circuit 1301 from the least significant digit to the most significant digit thereof into 2-digit groups and then recodes each of the 2-digit groups into a value of from -2 to 2. Reference numeral 1308 represents a binary number converting circuit which converts a redundant binary intermediate product outputted from the latch 1304 into a binary result of the multiplication. Reference numeral 1309 designates a rounding circuit which rounds and normalizes the result of the multiplication outputted from the binary conversion circuit 1308. Reference numeral 1310 indicates a redundant binary number subtracting circuit which performs the redundant binary addition of a redundant binary value latched by the selection latch 1301 to a predetermined constant A. Incidentally, when a binary number is inputted to the redundant binary addition circuit 1310, the device is adapted to set the constant A as 0.
Next, an operation of multiplying by a multiplicand by a value obtained by subtracting a redundant binary intermediate product from a predetermined constant A, which is effected by using the multiplication processing device of FIG. 13, will be described hereinbelow. In the equation (2), P.sub.n-1 is a redundant binary intermediate result obtained as a result of a multiplication effected in the cycle directly before the present cycle. This intermediate result is inputted from the latch 1301 to the redundant binary number subtracting circuit 1310. Simultaneously, the constant A is inputted to the redundant binary number subtracting circuit 1310 as another input value thereof. Then, the term (A-P.sub.n-1) of the equation (2) is calculated. Moreover, simultaneously, a multiplicand Q.sub.n-1 is inputted to the latch 1302 and subsequently the multiplication (A-P.sub.n-1).times.Q.sub.n-1 is effected.
Thus, in case of the above described conventional iterative multiplication processing device which effects a multiplication in each cycle by using the result of the multiplication obtained in the cycle directly before the present cycle, the redundant binary number subtracting circuit for subtracting the result of the multiplication effected in the cycle directly before the preset cycle from the constant A is required. Therefore, the third conventional iterative multiplication processing device has drawbacks that a multiplication execution rate becomes small and that the size of hardware becomes large.
In cases of the first to third conventional devices, the intermediate result is represented as a redundant binary number which is a kind of signed digital data. However, a multiplication circuit outputting an intermediate result by retaining or saving a carry and an iterative multiplication circuit using a high radix have the construction similar to that of the first, second or third conventional device.
As above described, the conventional iterative multiplication processing circuit, which performs a rounding operation on completion of each multiplication, (namely, the first conventional iterative multiplication processing circuit) should convert the intermediate result to binary data by using the binary number converting circuit and should then round the converted binary data by using the rounding circuit. Thus, the first conventional iterative multiplication processing circuit has defects that an iterative-multiplication execution rate is small, that the circuit size thereof becomes large and that power consumption becomes increased.
Moreover, the conventional iterative multiplication processing device, which multiplies a multiplicand by a value obtained by subtracting a multiplier from a constant A and using the result of the multiplication as a multiplier for the next multiplication, (namely, the second conventional iterative multiplication processing device) should subtract the result of the multiplication from the constant. Therefore, the second conventional iterative multiplication processing circuit has similar drawbacks that an iterative-multiplication execution rate becomes small, that the circuit size thereof becomes large and that power consumption becomes increased.
The present invention is accomplished to eliminate the defects of the conventional devices.
It is accordingly an object of the present invention to provide a multiplication processing device which can perform an iterative multiplication operation at a high speed and has a small-sized circuit and small power consumption and is suitable for an iterative multiplication.